Regular languages and partial commutations
Identifieur interne : 000419 ( France/Analysis ); précédent : 000418; suivant : 000420Regular languages and partial commutations
Auteurs : Antonio Cano [Espagne] ; Giovanna Guaiana [France] ; Jean-Eric Pin [France]Source :
English descriptors
- mix :
Abstract
The closure of a regular language under a [partial] commutation I has been extensively studied. We present new advances on two problems of this area: (1) When is the closure of a regular language under [partial] commutation still regular? (2) Are there any robust classes of languages closed under [partial] commutation? We show that the class Pol G of polynomials of group languages is closed under commutation, and under partial commutation when the complement of I in A^2 is a transitive relation. We also give a sufficient graph theoretic condition on I to ensure that the closure of a language of Pol G under I-commutation is regular. We exhibit a very robust class of languages W which is closed under commutation. This class contains Pol G and is decidable. It is also closed under intersection, union, shuffle, concatenation, quotients, length-decreasing morphisms and inverses of morphisms. If I is transitive, we show that the closure of a language of W under I-commutation is regular. The proofs are nontrivial and combine several advanced techniques, including combinatorial Ramsey type arguments, algebraic properties of the syntactic monoid, finiteness conditions on semigroups and properties of insertion systems.
Url:
DOI: 10.1016/j.ic.2013.07.003
Affiliations:
- Espagne, France
- Haute-Normandie, Région Normandie
- Le Havre, Rouen
- Université de Rouen, Université du Havre
Links toward previous steps (curation, corpus...)
- to stream Hal, to step Corpus: 000272
- to stream Hal, to step Curation: 000272
- to stream Hal, to step Checkpoint: 000262
- to stream Main, to step Merge: 000443
- to stream Main, to step Curation: 000444
- to stream Main, to step Exploration: 000444
- to stream France, to step Extraction: 000419
Links to Exploration step
Hal:hal-01247172Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Regular languages and partial commutations</title><author><name sortKey="Cano, Antonio" sort="Cano, Antonio" uniqKey="Cano A" first="Antonio" last="Cano">Antonio Cano</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-134328" status="VALID"><orgName>Departamento de Sistemas Informáticos y Computación [Valencia]</orgName><desc><address><addrLine>Camino de Vera, s/n 46022 Valencia</addrLine><country key="ES"></country></address><ref type="url">http://www.upv.es/entidades/DSIC/index-va.html</ref></desc><listRelation><relation active="#struct-300772" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-300772" type="direct"><org type="institution" xml:id="struct-300772" status="VALID"><orgName>Universidad Politécnica de Valencia</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle></tutelles></hal:affiliation><country>Espagne</country></affiliation></author><author><name sortKey="Guaiana, Giovanna" sort="Guaiana, Giovanna" uniqKey="Guaiana G" first="Giovanna" last="Guaiana">Giovanna Guaiana</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-23832" status="VALID"><orgName>Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes</orgName><orgName type="acronym">LITIS</orgName><desc><address><addrLine>Avenue de l'Université UFR des Sciences et Techniques 76800 Saint-Etienne du Rouvray</addrLine><country key="FR"></country></address><ref type="url">http://www.litislab.eu</ref></desc><listRelation><relation active="#struct-300317" type="direct"></relation><relation name="EA4108" active="#struct-300318" type="direct"></relation><relation active="#struct-301288" type="direct"></relation><relation active="#struct-301232" type="indirect"></relation></listRelation><tutelles><tutelle active="#struct-300317" type="direct"><org type="institution" xml:id="struct-300317" status="VALID"><orgName>Université du Havre</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle name="EA4108" active="#struct-300318" type="direct"><org type="institution" xml:id="struct-300318" status="VALID"><orgName>Université de Rouen</orgName><desc><address><addrLine> 1 rue Thomas Becket - 76821 Mont-Saint-Aignan</addrLine><country key="FR"></country></address><ref type="url">http://www.univ-rouen.fr/</ref></desc></org></tutelle><tutelle active="#struct-301288" type="direct"><org type="department" xml:id="struct-301288" status="VALID"><orgName>Institut National des Sciences Appliquées - Rouen</orgName><orgName type="acronym">INSA Rouen</orgName><desc><address><country key="FR"></country></address></desc><listRelation><relation active="#struct-301232" type="direct"></relation></listRelation></org></tutelle><tutelle active="#struct-301232" type="indirect"><org type="institution" xml:id="struct-301232" status="VALID"><orgName>Institut National des Sciences Appliquées</orgName><orgName type="acronym">INSA</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Le Havre</settlement><region type="region" nuts="2">Région Normandie</region><region type="old region" nuts="2">Haute-Normandie</region></placeName><orgName type="university">Université du Havre</orgName><placeName><settlement type="city">Rouen</settlement><region type="region" nuts="2">Région Normandie</region><region type="old region" nuts="2">Haute-Normandie</region></placeName><orgName type="university">Université de Rouen</orgName></affiliation></author><author><name sortKey="Pin, Jean Eric" sort="Pin, Jean Eric" uniqKey="Pin J" first="Jean-Eric" last="Pin">Jean-Eric Pin</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-1033" status="OLD"><orgName>Laboratoire d'informatique Algorithmique : Fondements et Applications</orgName><orgName type="acronym">LIAFA</orgName><date type="end">2015-12-31</date><desc><address><addrLine>Université Paris Diderot, Bât. Sophie Germain, case postale 7014, 75205 Paris cedex 13</addrLine><country key="FR"></country></address><ref type="url">http://www.liafa.jussieu.fr/</ref></desc><listRelation><relation active="#struct-300301" type="direct"></relation><relation name="UMR7089" active="#struct-441569" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-300301" type="direct"><org type="institution" xml:id="struct-300301" status="VALID"><orgName>Université Paris Diderot - Paris 7</orgName><orgName type="acronym">UP7</orgName><desc><address><addrLine>5 rue Thomas-Mann - 75205 Paris cedex 13</addrLine><country key="FR"></country></address><ref type="url">http://www.univ-paris-diderot.fr</ref></desc></org></tutelle><tutelle name="UMR7089" active="#struct-441569" type="direct"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle></tutelles></hal:affiliation><country>France</country></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">HAL</idno><idno type="RBID">Hal:hal-01247172</idno><idno type="halId">hal-01247172</idno><idno type="halUri">https://hal.archives-ouvertes.fr/hal-01247172</idno><idno type="url">https://hal.archives-ouvertes.fr/hal-01247172</idno><idno type="doi">10.1016/j.ic.2013.07.003</idno><date when="2013">2013</date><idno type="wicri:Area/Hal/Corpus">000272</idno><idno type="wicri:Area/Hal/Curation">000272</idno><idno type="wicri:Area/Hal/Checkpoint">000262</idno><idno type="wicri:Area/Main/Merge">000443</idno><idno type="wicri:Area/Main/Curation">000444</idno><idno type="wicri:Area/Main/Exploration">000444</idno><idno type="wicri:Area/France/Extraction">000419</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">Regular languages and partial commutations</title><author><name sortKey="Cano, Antonio" sort="Cano, Antonio" uniqKey="Cano A" first="Antonio" last="Cano">Antonio Cano</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-134328" status="VALID"><orgName>Departamento de Sistemas Informáticos y Computación [Valencia]</orgName><desc><address><addrLine>Camino de Vera, s/n 46022 Valencia</addrLine><country key="ES"></country></address><ref type="url">http://www.upv.es/entidades/DSIC/index-va.html</ref></desc><listRelation><relation active="#struct-300772" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-300772" type="direct"><org type="institution" xml:id="struct-300772" status="VALID"><orgName>Universidad Politécnica de Valencia</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle></tutelles></hal:affiliation><country>Espagne</country></affiliation></author><author><name sortKey="Guaiana, Giovanna" sort="Guaiana, Giovanna" uniqKey="Guaiana G" first="Giovanna" last="Guaiana">Giovanna Guaiana</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-23832" status="VALID"><orgName>Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes</orgName><orgName type="acronym">LITIS</orgName><desc><address><addrLine>Avenue de l'Université UFR des Sciences et Techniques 76800 Saint-Etienne du Rouvray</addrLine><country key="FR"></country></address><ref type="url">http://www.litislab.eu</ref></desc><listRelation><relation active="#struct-300317" type="direct"></relation><relation name="EA4108" active="#struct-300318" type="direct"></relation><relation active="#struct-301288" type="direct"></relation><relation active="#struct-301232" type="indirect"></relation></listRelation><tutelles><tutelle active="#struct-300317" type="direct"><org type="institution" xml:id="struct-300317" status="VALID"><orgName>Université du Havre</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle name="EA4108" active="#struct-300318" type="direct"><org type="institution" xml:id="struct-300318" status="VALID"><orgName>Université de Rouen</orgName><desc><address><addrLine> 1 rue Thomas Becket - 76821 Mont-Saint-Aignan</addrLine><country key="FR"></country></address><ref type="url">http://www.univ-rouen.fr/</ref></desc></org></tutelle><tutelle active="#struct-301288" type="direct"><org type="department" xml:id="struct-301288" status="VALID"><orgName>Institut National des Sciences Appliquées - Rouen</orgName><orgName type="acronym">INSA Rouen</orgName><desc><address><country key="FR"></country></address></desc><listRelation><relation active="#struct-301232" type="direct"></relation></listRelation></org></tutelle><tutelle active="#struct-301232" type="indirect"><org type="institution" xml:id="struct-301232" status="VALID"><orgName>Institut National des Sciences Appliquées</orgName><orgName type="acronym">INSA</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Le Havre</settlement><region type="region" nuts="2">Région Normandie</region><region type="old region" nuts="2">Haute-Normandie</region></placeName><orgName type="university">Université du Havre</orgName><placeName><settlement type="city">Rouen</settlement><region type="region" nuts="2">Région Normandie</region><region type="old region" nuts="2">Haute-Normandie</region></placeName><orgName type="university">Université de Rouen</orgName></affiliation></author><author><name sortKey="Pin, Jean Eric" sort="Pin, Jean Eric" uniqKey="Pin J" first="Jean-Eric" last="Pin">Jean-Eric Pin</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-1033" status="OLD"><orgName>Laboratoire d'informatique Algorithmique : Fondements et Applications</orgName><orgName type="acronym">LIAFA</orgName><date type="end">2015-12-31</date><desc><address><addrLine>Université Paris Diderot, Bât. Sophie Germain, case postale 7014, 75205 Paris cedex 13</addrLine><country key="FR"></country></address><ref type="url">http://www.liafa.jussieu.fr/</ref></desc><listRelation><relation active="#struct-300301" type="direct"></relation><relation name="UMR7089" active="#struct-441569" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-300301" type="direct"><org type="institution" xml:id="struct-300301" status="VALID"><orgName>Université Paris Diderot - Paris 7</orgName><orgName type="acronym">UP7</orgName><desc><address><addrLine>5 rue Thomas-Mann - 75205 Paris cedex 13</addrLine><country key="FR"></country></address><ref type="url">http://www.univ-paris-diderot.fr</ref></desc></org></tutelle><tutelle name="UMR7089" active="#struct-441569" type="direct"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle></tutelles></hal:affiliation><country>France</country></affiliation></author></analytic><idno type="DOI">10.1016/j.ic.2013.07.003</idno></biblStruct></sourceDesc></fileDesc><profileDesc><textClass><keywords scheme="mix" xml:lang="en"><term> regular language</term><term> traces</term><term>partial commutation</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">The closure of a regular language under a [partial] commutation I has been extensively studied. We present new advances on two problems of this area: (1) When is the closure of a regular language under [partial] commutation still regular? (2) Are there any robust classes of languages closed under [partial] commutation? We show that the class Pol G of polynomials of group languages is closed under commutation, and under partial commutation when the complement of I in A^2 is a transitive relation. We also give a sufficient graph theoretic condition on I to ensure that the closure of a language of Pol G under I-commutation is regular. We exhibit a very robust class of languages W which is closed under commutation. This class contains Pol G and is decidable. It is also closed under intersection, union, shuffle, concatenation, quotients, length-decreasing morphisms and inverses of morphisms. If I is transitive, we show that the closure of a language of W under I-commutation is regular. The proofs are nontrivial and combine several advanced techniques, including combinatorial Ramsey type arguments, algebraic properties of the syntactic monoid, finiteness conditions on semigroups and properties of insertion systems. </div></front></TEI><affiliations><list><country><li>Espagne</li><li>France</li></country><region><li>Haute-Normandie</li><li>Région Normandie</li></region><settlement><li>Le Havre</li><li>Rouen</li></settlement><orgName><li>Université de Rouen</li><li>Université du Havre</li></orgName></list><tree><country name="Espagne"><noRegion><name sortKey="Cano, Antonio" sort="Cano, Antonio" uniqKey="Cano A" first="Antonio" last="Cano">Antonio Cano</name></noRegion></country><country name="France"><region name="Région Normandie"><name sortKey="Guaiana, Giovanna" sort="Guaiana, Giovanna" uniqKey="Guaiana G" first="Giovanna" last="Guaiana">Giovanna Guaiana</name></region><name sortKey="Pin, Jean Eric" sort="Pin, Jean Eric" uniqKey="Pin J" first="Jean-Eric" last="Pin">Jean-Eric Pin</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/France/explor/LeHavreV1/Data/France/Analysis
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000419 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/France/Analysis/biblio.hfd -nk 000419 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/France
|area= LeHavreV1
|flux= France
|étape= Analysis
|type= RBID
|clé= Hal:hal-01247172
|texte= Regular languages and partial commutations
}}
| This area was generated with Dilib version V0.6.25. |  |